﻿// 4559. 老鼠吃奶酪.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>


using namespace std;
/*

https://www.acwing.com/problem/content/4562/
给定一个 n行 n 列的方格矩阵。

每个方格中都有一定数量的奶酪。

初始时，第 1 行第 1 列的方格（左上角方格）中有一只老鼠。

在它吃完这个方格中的奶酪后，它将开始移动。

每次移动可以朝一个方向（上、下、左、右）前进最多不超过 k 格距离。

移动时需要注意：

不能走到矩阵外。
每次移动抵达的方格中包含的奶酪数量必须大于移动前所在的方格中包含的奶酪数量。
每当老鼠抵达一个方格后，就可以吃掉该方格中的所有奶酪。

请问，老鼠通过合理移动，最多可以吃掉多少奶酪。

输入格式
输入包含多组数据。

每组数据第一行包含两个整数 n,k。

接下来 n 行，每行包含 n 个整数，
其中第 i 行第 j 列的整数表示第 i行第 j 列的方格中的奶酪数量。

当输入一行 -1 -1 时，表示输入结束。

输出格式
每组数据输出一行答案，一个整数，表示可以吃掉的最大奶酪数量。

数据范围
1≤n,k≤100。
每个方格中奶酪的数量范围 [0,100]。

输入样例：
3 1
1 2 5
10 11 6
12 12 7
-1 -1
输出样例：
37
*/

const int N = 105;
int graph[N][N];
int dp[N][N];  
int n, k;

int dfs(int x, int y) {
	int limit; memset(&limit, -0x3f, sizeof limit);
	if (dp[x][y] != limit) return dp[x][y];

	dp[x][y] = 0;

	for (int i = x - k; i <= x + k; i++) {
		if (i == x || i <= 0 || i > n) continue;
		if(graph[i][y] > graph[x][y])
			dp[x][y] = max(dp[x][y], dfs(i, y));
	}

	for (int i = y - k; i <= y + k; i++) {
		if (i == y || i <= 0 || i > n) continue;
		if (graph[x][i] > graph[x][y])
			dp[x][y] = max(dp[x][y], dfs(x, i));
	}

	dp[x][y] += graph[x][y];
	return dp[x][y];
}


int main()
{
	while (cin >> n >> k) {
		if (-1 == n && -1 == k) break;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> graph[i][j];
			}
		}
		memset(dp, -0x3f, sizeof dp);

		cout << dfs(1, 1) << endl;
	}

	return 0;
}

 